package Intermediate_algorithm.Backtracking;

import org.junit.Test;

import java.util.Arrays;

/*
单词搜索
给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvkwe2/
 */
public class _05单词搜索 {
    
    @Test
    public void test() {
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
        System.out.println(exist(board, "ABCESEEEFS"));
    }

    //回溯
    //ps: 终止条件要完整，回溯的撤销处理不要忘了，并且撤销处理应该在所有递归之后，
    // 即递归到否决该支路的时候进行一次撤回，这样根据递归特性，他会不断撤回

    /*
    第一个优化
    比如示例 3，word=ABCB，其中字母 B 出现了 2 次，但 board 中只有 1 个字母 B，所以肯定搜不到 word，直接返回 false。
    一般地，如果 word 的某个字母的出现次数，比 board 中的这个字母的出现次数还要多，可以直接返回 false。
    第二个优化
    设 word 的第一个字母在 board 中的出现了 x 次，word 的最后一个字母在 board 中的出现了 y 次。
    如果 y<x，我们可以把 word 反转，相当于从 word 的最后一个字母开始搜索，这样更多的时候一开始就匹配失败，递归的总次数更少。
    加上这两个优化，就可以击败接近 100% 了！
     */
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean backtrack = backtrack(board, visited, j, i, word, new StringBuilder(), 0);
                if (backtrack)
                    return true;
            }
        }
        return false;
    }

    public boolean backtrack(char[][]board,boolean[][] visited,int x,int y,String word,StringBuilder sb,int index) {
        if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || visited[y][x] ||index >= word.length() ||board[y][x] != word.charAt(index)) {
            return false;
        }
        sb.append(board[y][x]);
        visited[y][x] = true;
        if (sb.length() == word.length()) {
            return true;
        }

        boolean b1 = backtrack(board, visited, x + 1, y, word, sb, index + 1);
        boolean b2 = backtrack(board, visited, x - 1, y, word, sb, index + 1);
        boolean b3 = backtrack(board, visited, x, y + 1, word, sb, index + 1);
        boolean b4 = backtrack(board, visited, x, y - 1, word, sb, index + 1);
        visited[y][x] = false;
        sb.deleteCharAt(sb.length() - 1);
        return b1 || b2 || b3 || b4;
    }

    //官解：方法一：回溯
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/word-search/solutions/411613/dan-ci-sou-suo-by-leetcode-solution/
     */
    class Solution {
        public boolean exist(char[][] board, String word) {
            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
            if (board[i][j] != s.charAt(k)) {
                return false;
            } else if (k == s.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            boolean result = false;
            for (int[] dir : directions) {
                int newi = i + dir[0], newj = j + dir[1];
                if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                    if (!visited[newi][newj]) {
                        boolean flag = check(board, visited, newi, newj, s, k + 1);
                        if (flag) {
                            result = true;
                            break;
                        }
                    }
                }
            }
            visited[i][j] = false;
            return result;
        }
    }


}
